The present invention relates generally to the coding of digital multimedia data. More particularly, the invention relates to error resilient coding of digital multimedia data for maintaining signal quality in a noisy system, or overcoming data loss without re-transmission.
Digital multimedia data may be coded in either variable-length segments, such as MPEG data or in fixed-length segments, such as digital video (DV) data. Digital multimedia data coded in fixed-length segments, however, may include both: digital multimedia data coded using fixed-length coding techniques; and digital multimedia data coded using variable-length coding techniques, such as run length coding, in fixed-length segments.
With the explosive growth of the Internet, there is a growing interest in using the Internet and other Internet protocol-based networks to deliver multimedia selections, such as video and audio material. Interactive television, movies on demand, and other multimedia push technologies are among the more promising applications.
The Internet is a connectionless network offering best effort delivery service. Packets of data are routed as datagrams that carry the address of the intended recipient. A specific connection between the sender and the recipient is not required, because all host nodes on the network include the inherent capability to route datagrams from node to node until delivery is effected. This packet delivery scheme is constructed as a best effort delivery system in which the delivery of packets is not guaranteed. Additionally, certain transmission channels through such a network may have higher channel quality and thus inherently lose fewer packets. Higher quality channels are often more expense to use and may be under greater demand, both of which may effect the desirability of using such channels. These facts significantly affect how certain multimedia data are delivered.
A number of schemes have been designed to deal with the difficulties of transmitting multimedia data arising from possible the loss of packets during transmission. One such scheme is described in U.S. Pat. No. 5,928,331 to Bushmitch. In this scheme, the video data is coded using a non-hierarchical coding technique in which the data are capable of being reconstituted from fewer than all of the components of the original data stream. Image quality is dependent on the number of components used for the reconstitution.
Another method involves the retransmission of lost packets. Re-transmission has usually been the method of choice for dealing with lost packets of digital multimedia data coded in fixed-length segments. The client receiving the data requests the re-transmission of any packets which do not arrive within a reasonable time frame. The arrival of the re-transmitted data is also not guaranteed, which may require further re-transmission. For video data, this method may lead to significant time lags in viewing the images and possible choppiness for streaming video applications. The eventual image quality is maintained, though, due to the availability of all original data for reconstitution and decoding.
Error concealment and error correction methods have also been used to repair audio and video data with missing packets. These methods are often used in conjunction, with errors being corrected if possible and concealed if correction is not possible. Also, error concealment and error correction methods have proven useful for recovering data which has been corrupted during storage, such as data from a CD or DVD which contains a scratch or other defect, or due to noise during transmission. Error concealment methods fill in missing data in a file with replacement data. Replacement data may be zeroes or may be determined by interpolating nearby data to obtain values. For video data, the use of zeroes for replacement data may lead to a section of black pixels in an image, while interpolation may lower the resolution of the image by smearing the area containing the error. Error correction involves the inclusion of additional data, along with the original data, which may allow the detection and possible recovery of missing or corrupted data. Error correction increases the amount of data and may increase necessary decoding time or resources, but it allows for a certain degree of data loss or corruption while maintaining image quality.
A common form of error correction that has been used with MPEG data is forward error correction (FEC). In traditional FEC coding the original data is thought of as being organized into channel blocks, as shown in FIG. 1. Channel block 100 is a matrix of rows 102 and columns 106 with the data organized in successive rows of a set length. An FEC formula, such as a Reed-Solomon code, is applied to each row to generate FEC data 104 for that row. As shown, FEC data 104 is arranged as a column at the end of each row. The data is then separated into columns so that it may be stored or transmitted. Each column represents one transmission packet. By applying the FEC formula in a direction orthogonal to the packetization the FEC method may allow for the recovery of lost packets as well as correction of errors due to noise or data corruption (unless more than a certain number of packets are lost). When this interleaving scheme is applied to block-based video data such as DV data, unrecoverable packet losses (when the FEC is not strong enough) may cause many video blocks to become undecodable.
In Video Streaming: An FEC-Based Novel Approach, Cai and Chen disclose an alternative method of forming the channel block for FEC coding of MPEG-4 video data, known as pre-interleaving. As shown in FIG. 2, data is arranged in consecutive columns 202 of channel block 200 rather than along rows 204 as illustrated in FIG. 1. The data is still separated into columns for storage or transmission, i.e. packetization remains orthogonal to the FEC coding, but the pre-interleaved data is now aligned with the packetization. This means that each packet contains consecutive data. Pre-interleaving is used in this method due to the variable length coding of the data. Therefore, any non-correctable errors due to a lost or corrupted packet will be grouped in the MPEG-4 video image. This grouping of non-correctable errors may improve error concealment for MPEG-4 video data.